{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Smallest Subarrays With Maximum Bitwise OR"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #binary-search #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #二分查找 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: smallestSubarrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #按位或最大的最小子数组长度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个长度为 <code>n</code>&nbsp;下标从 <strong>0</strong>&nbsp;开始的数组&nbsp;<code>nums</code>&nbsp;，数组中所有数字均为非负整数。对于&nbsp;<code>0</code>&nbsp;到&nbsp;<code>n - 1</code>&nbsp;之间的每一个下标 <code>i</code>&nbsp;，你需要找出&nbsp;<code>nums</code>&nbsp;中一个 <strong>最小</strong> 非空子数组，它的起始位置为&nbsp;<code>i</code>&nbsp;（包含这个位置），同时有&nbsp;<strong>最大</strong>&nbsp;的 <strong>按位或</strong><b>运算值</b>&nbsp;。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>换言之，令&nbsp;<code>B<sub>ij</sub></code>&nbsp;表示子数组&nbsp;<code>nums[i...j]</code>&nbsp;的按位或运算的结果，你需要找到一个起始位置为&nbsp;<code>i</code>&nbsp;的最小子数组，这个子数组的按位或运算的结果等于&nbsp;<code>max(B<sub>ik</sub>)</code>&nbsp;，其中&nbsp;<code>i &lt;= k &lt;= n - 1</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>一个数组的按位或运算值是这个数组里所有数字按位或运算的结果。</p>\n",
    "\n",
    "<p>请你返回一个大小为 <code>n</code>&nbsp;的整数数组<em>&nbsp;</em><code>answer</code>，其中<em>&nbsp;</em><code>answer[i]</code>是开始位置为&nbsp;<code>i</code>&nbsp;，按位或运算结果最大，且&nbsp;<strong>最短</strong>&nbsp;子数组的长度。</p>\n",
    "\n",
    "<p><strong>子数组</strong>&nbsp;是数组里一段连续非空元素组成的序列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [1,0,2,1,3]\n",
    "<b>输出：</b>[3,3,2,2,1]\n",
    "<strong>解释：</strong>\n",
    "任何位置开始，最大按位或运算的结果都是 3 。\n",
    "- 下标 0 处，能得到结果 3 的最短子数组是 [1,0,2] 。\n",
    "- 下标 1 处，能得到结果 3 的最短子数组是 [0,2,1] 。\n",
    "- 下标 2 处，能得到结果 3 的最短子数组是 [2,1] 。\n",
    "- 下标 3 处，能得到结果 3 的最短子数组是 [1,3] 。\n",
    "- 下标 4 处，能得到结果 3 的最短子数组是 [3] 。\n",
    "所以我们返回 [3,3,2,2,1] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [1,2]\n",
    "<b>输出：</b>[2,1]\n",
    "<strong>解释：\n",
    "</strong>下标 0 处，能得到最大按位或运算值的最短子数组长度为 2 。\n",
    "下标 1 处，能得到最大按位或运算值的最短子数组长度为 1 。\n",
    "所以我们返回 [2,1] 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [smallest-subarrays-with-maximum-bitwise-or](https://leetcode.cn/problems/smallest-subarrays-with-maximum-bitwise-or/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [smallest-subarrays-with-maximum-bitwise-or](https://leetcode.cn/problems/smallest-subarrays-with-maximum-bitwise-or/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,0,2,1,3]', '[1,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        res = [0] * n\n",
    "        bits = [0] * 32\n",
    "        for i in range(n-1, -1, -1):\n",
    "            s = bin(nums[i])[2:][::-1]\n",
    "            for j, c in enumerate(s):\n",
    "                if c == '1':\n",
    "                    bits[-j] = i\n",
    "            res[i] = max(max(bits) - i + 1, 1)\n",
    "\n",
    "        return res\n",
    "               "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n",
    "        '''\n",
    "        位运算的重要性质：\n",
    "        当前位的位运算结果跟其他位无关\n",
    "        最大或子数组\n",
    "        根据或运算的性质，由于子数组长度很大，必然会有很多重复的值\n",
    "        只需要在这些值中找到最后一个即可\n",
    "        '''\n",
    "        n=len(nums)\n",
    "        ans=[0]*n\n",
    "        s={}\n",
    "        for i in range(n-1,-1,-1):\n",
    "            x=nums[i]\n",
    "            t=s.copy()\n",
    "            s={}\n",
    "            for y,idy in t.items():\n",
    "                s[y|x]=idy\n",
    "            s[x]=i\n",
    "            or_=max(s.keys())\n",
    "            ans[i]=s[or_]-i+1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n",
    "        '''\n",
    "        位运算的重要性质：\n",
    "        当前位的位运算结果跟其他位无关\n",
    "        最大或子数组\n",
    "        根据或运算的性质，由于子数组长度很大，必然会有很多重复的值（去重思想）\n",
    "        每次循环最多多少次？\n",
    "        答：31次，x要么不变，要么某些bit位由0变成1,字典最多有31个数\n",
    "        只需要在这些值中找到最后一个即可\n",
    "        '''\n",
    "        n=len(nums)\n",
    "        ans=[0]*n\n",
    "        s={}\n",
    "        for i in range(n-1,-1,-1):\n",
    "            x=nums[i]\n",
    "            t=s.copy()\n",
    "            s={}\n",
    "            for y,idy in t.items():\n",
    "                s[y|x]=idy\n",
    "            s[x]=i\n",
    "            or_=max(s.keys())\n",
    "            ans[i]=s[or_]-i+1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [0] * n\n",
    "        ors = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            num = nums[i]\n",
    "            ors.append([0, i])\n",
    "            for p in ors:\n",
    "                p[0] |= num # 都或上num\n",
    "            k = 0\n",
    "            for p in ors:\n",
    "                if p[0] != ors[k][0]:\n",
    "                    k += 1\n",
    "                    ors[k] = p\n",
    "                else:\n",
    "                    ors[k][1] = p[1]\n",
    "            del ors[k + 1:]\n",
    "            ans[i] = ors[0][1] - i + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n",
    "        res = [0] * len(nums)\n",
    "        for i,x in enumerate(nums):\n",
    "            res[i] = 1\n",
    "            for j in range(i - 1,-1,-1):\n",
    "                if (nums[j] | x) == nums[j]:\n",
    "                    break\n",
    "                nums[j] |= x\n",
    "                res[j] = i - j + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n",
    "        ans = [0] * len(nums)\n",
    "        for i, x in enumerate(nums):\n",
    "            ans[i] = 1\n",
    "            for j in range(i - 1, -1, -1):\n",
    "                if (nums[j] | x) == nums[j]:\n",
    "                    break\n",
    "                nums[j] |= x\n",
    "                ans[j] = i - j + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n",
    "        # 超时\n",
    "        #找出一个最小的非空子数组，同时它具有最大的或运算值\n",
    "        # # 要得到的最大按位或运算结果\n",
    "        # #滑动窗口\n",
    "        # max_ans=-math.inf\n",
    "        # min_length=0\n",
    "        # left,right=0,0\n",
    "        # res=[]\n",
    "        # for left in range(len(nums)):\n",
    "        #     ans =0\n",
    "        #     for right in range(left,len(nums)):\n",
    "        #         #如果获取到最大值就改变一次\n",
    "        #         ans |=nums[right]\n",
    "        #         if ans > max_ans:\n",
    "        #             max_ans=max(max_ans,ans)\n",
    "        #             min_length=right-left+1\n",
    "        #     max_ans=0\n",
    "        #     res.append(min_length)\n",
    "        # return res\n",
    "        ans =[0 for _ in range(len(nums))]\n",
    "        res =[0 for _ in range(32)]\n",
    "        n=len(nums)\n",
    "        for i in range(n-1,-1,-1):\n",
    "            cur=nums[i]\n",
    "            for j in range(32):\n",
    "                if cur &(1<<j):\n",
    "                    res[j]=i\n",
    "            need_max =i\n",
    "            for j in range(32):\n",
    "                need_max = max(need_max,res[j])\n",
    "            ans[i] = need_max -i+1\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [0] * n\n",
    "        tmp = [0] * 32\n",
    "        k = n - 1\n",
    "        # flag = False\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            flag = False\n",
    "            for j in range(32):\n",
    "                tmp[j] += (nums[i] >> j) & 1\n",
    "            while k > i:\n",
    "                for j in range(32):\n",
    "                    if tmp[j] == 1 and (nums[k] >> j) & 1:\n",
    "                        flag = True\n",
    "                        break\n",
    "                if flag:\n",
    "                    break\n",
    "                for j in range(32):\n",
    "                    tmp[j] -= (nums[k] >> j) & 1\n",
    "                k -= 1\n",
    "            # print(i, j, k, tmp)\n",
    "            ans[i] = k - i + 1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n",
    "        \"\"\"\n",
    "            非负整数 \n",
    "            起始地址为 i\n",
    "        \"\"\"\n",
    "        ans = [0] *len(nums)\n",
    "\n",
    "        for i ,x in enumerate(nums):\n",
    "            ans[i] = 1\n",
    "            for j in range(i-1,-1,-1):\n",
    "                if (nums[j]|x) == nums[j]:\n",
    "                    break\n",
    "                nums[j] |=x\n",
    "                ans[j] = i-j+1\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n",
    "        ans = [0] * len(nums)\n",
    "        for i, x in enumerate(nums):\n",
    "            ans[i] = 1\n",
    "            for j in range(i - 1, -1, -1):\n",
    "                if (nums[j] | x) == nums[j]:\n",
    "                    break\n",
    "                nums[j] |= x\n",
    "                ans[j] = i - j + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n",
    "        ans = [0] * len(nums)\n",
    "        for i, x in enumerate(nums):\n",
    "            ans[i] = 1\n",
    "            for j in range(i - 1, -1, -1):\n",
    "                if (nums[j] | x) == nums[j]:\n",
    "                    break\n",
    "                nums[j] |= x\n",
    "                ans[j] = i - j + 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n",
    "        ans = [0] * len(nums)\n",
    "        for i, x in enumerate(nums):\n",
    "            ans[i] = 1\n",
    "            for j in range(i - 1, -1, -1):\n",
    "                if (nums[j] | x) == nums[j]:\n",
    "                    break\n",
    "                nums[j] |= x\n",
    "                ans[j] = i - j + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import *\n",
    "from queue import PriorityQueue\n",
    "from typing import *\n",
    "from heapq import *\n",
    "from functools import lru_cache\n",
    "# by hangpengjie\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [0] * n\n",
    "        a = []\n",
    "        for i in range(n-1,-1,-1):\n",
    "            x = nums[i]\n",
    "            a.append([0,i])\n",
    "            k = 0\n",
    "            for p in a:\n",
    "                p[0] |= x\n",
    "                if a[k][0] == p[0]:\n",
    "                    a[k][1] = p[1]\n",
    "                else:\n",
    "                    k+= 1\n",
    "                    a[k] = p\n",
    "            del a[k+1:]\n",
    "            ans[i] = (a[0][1] - i + 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [0] * n\n",
    "        ors = []  # 按位或的值 + 对应子数组的右端点的最小值\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            num = nums[i]\n",
    "            ors.append([0, i])\n",
    "            k = 0\n",
    "\n",
    "            for p in ors:\n",
    "                p[0] |= num\n",
    "\n",
    "            idx=0\n",
    "            for j in range(1,len(ors)):\n",
    "                if ors[j][0]<ors[j-1][0]:\n",
    "                    idx+=1\n",
    "                ors[idx]=ors[j]\n",
    "            del ors[idx + 1:]\n",
    "\n",
    "            # 本题只用到了 ors[0]，如果题目改成任意给定数值，可以在 ors 中查找\n",
    "            ans[i] = ors[0][1] - i + 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ors = []\n",
    "        ans = [0] * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            num = nums[i]\n",
    "            ors.append([0, i])\n",
    "            k = 0\n",
    "            for p in ors:\n",
    "                p[0] |= num\n",
    "                if p[0] == ors[k][0]:\n",
    "                    ors[k] = p\n",
    "                else:\n",
    "                    k += 1\n",
    "                    ors[k] = p\n",
    "            del ors[k + 1:]\n",
    "            ans[i] = ors[0][1] - i + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [0]*n\n",
    "        ors = []\n",
    "        for i in range(n-1,-1,-1):\n",
    "            num = nums[i]\n",
    "            ors.append([0,i])\n",
    "            k = 0\n",
    "            for p in ors:\n",
    "                p[0] |= num\n",
    "                if ors[k][0] == p[0]:\n",
    "                    ors[k][1] = p[1]\n",
    "                else:\n",
    "                    k += 1\n",
    "                    ors[k] = p\n",
    "            del ors[k+1:]\n",
    "            ans[i] = ors[0][1]-i+1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [0] * n \n",
    "        ors = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            x = nums[i]\n",
    "            ors.append([0, i])\n",
    "            k = 0\n",
    "            for p in ors:\n",
    "                p[0] |= x\n",
    "                if ors[k][0] == p[0]:\n",
    "                    ors[k][1] = p[1]\n",
    "                else:\n",
    "                    k += 1\n",
    "                    ors[k] = p\n",
    "            del ors[k + 1:]\n",
    "            ans[i] = ors[0][1] - i + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [0] * n\n",
    "        ors = []\n",
    "        for i in range(n-1,-1,-1):\n",
    "            num = nums[i]\n",
    "            ors.append([0,i])\n",
    "            k = 0\n",
    "            for o in ors:\n",
    "                o[0] |= num\n",
    "                if o[0] == ors[k][0]:\n",
    "                    ors[k][1] = o[1]\n",
    "                else:\n",
    "                    k+=1\n",
    "                    ors[k] = o\n",
    "            del ors[k+1:]\n",
    "            # print(ors)\n",
    "            ans[i] = ors[0][1]-i+1\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n",
    "        dp = [-1] * 30  # 从右到左，记录每一位1的位置, -1表示没有1\n",
    "        n = len(nums)\n",
    "        ans = [1] * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            mx = 1\n",
    "            for k in range(30):\n",
    "                if nums[i] >> k & 1:\n",
    "                    dp[k] = i  # 更新第k位最新1的位置\n",
    "                if dp[k] != -1:\n",
    "                    mx = max(mx, dp[k] - i + 1)\n",
    "            ans[i] = mx\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [0]*n\n",
    "        ors = []\n",
    "        for i in range(n-1,-1,-1):\n",
    "            num = nums[i]\n",
    "            ors.append([0,i])\n",
    "            k = 0\n",
    "            for p in ors:\n",
    "                p[0] |= num\n",
    "                if ors[k][0] == p[0]:\n",
    "                    ors[k][1] = p[1]\n",
    "                else:\n",
    "                    k += 1\n",
    "                    ors[k] = p\n",
    "            del ors[k+1:]\n",
    "            ans[i] = ors[0][1]-i+1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        indexed = [-1] * 32\n",
    "        ans = [0] * n\n",
    "        # 记录每一位出现的位置 没有出现的记录为 n\n",
    "        for index in range(n - 1, -1, -1):  \n",
    "            item = nums[index]\n",
    "            r = index\n",
    "            for i in range(32):\n",
    "                if item >> i & 1 == 1:\n",
    "                    indexed[i] = index\n",
    "                if indexed[i] != -1:\n",
    "                    r = max(r, indexed[i])\n",
    "            ans[index] = r - index + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n",
    "        # ans = [1] * len(nums)\n",
    "        # for i, num in enumerate(nums):\n",
    "        #     for j in range(i-1, -1, -1):\n",
    "        #         if (nums[j] | num) == nums[j]: break\n",
    "        #         nums[j] |= num\n",
    "        #         ans[j] = i - j + 1\n",
    "        # return ans\n",
    "        ors = []\n",
    "        n = len(nums)\n",
    "        ans = [1] * n\n",
    "        for i in range(n-1, -1, -1):\n",
    "            num = nums[i]\n",
    "            ors.append([0, i])\n",
    "            j = 0\n",
    "            for p in ors:\n",
    "                p[0] |= num\n",
    "                if ors[j][0] == p[0]:\n",
    "                    ors[j][1] = p[1]\n",
    "                else:\n",
    "                    j += 1\n",
    "                    ors[j] = p\n",
    "\n",
    "            del ors[j+1:]\n",
    "            ans[i] = ors[0][1] - i + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n",
    "        L = len(nums)\n",
    "        last = 0\n",
    "        bit2off = {\n",
    "            1<<i: i for i in range(32)\n",
    "        }\n",
    "        posByBit = [L]*32\n",
    "        res = [0]*L\n",
    "        for i in range(L-1, -1, -1):\n",
    "            n = nums[i]\n",
    "            last |= n\n",
    "            while n:\n",
    "                bit = n & -n\n",
    "                posByBit[bit2off[bit]] = i\n",
    "                n -= bit\n",
    "            n, off = last, i\n",
    "            while n:\n",
    "                bit = n & -n\n",
    "                off = max(off, posByBit[bit2off[bit]])\n",
    "                n -= bit\n",
    "            res[i] = off -i + 1\n",
    "        return res\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:          \n",
    "                def check(f,t):\n",
    "                    for i,j in zip(f,t):    \n",
    "                        if i and j<=0:return False\n",
    "                    return True\n",
    "                            \n",
    "                n = len(nums)\n",
    "                f = [0] * 32\n",
    "                t = [0] * 32\n",
    "                for i in range(n):\n",
    "                    for j in range(31):\n",
    "                        f[j] += (nums[i]>>j&1)\n",
    "                ans = [1] * n; r = -1\n",
    "                for i in range(n):\n",
    "                    while not check(f,t) and r + 1 < n:\n",
    "                        r += 1\n",
    "                        for j in range(31):\n",
    "                            t[j] += (nums[r]>>j&1)\n",
    "                        \n",
    "                    ans[i] = max(ans[i],r - i + 1)\n",
    "                    for j in range(31):\n",
    "                        f[j] -= (nums[i]>>j&1)\n",
    "                        t[j] -= (nums[i]>>j&1)\n",
    "                return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [0]*n\n",
    "        cnt = [-1]*32\n",
    "        for i in range(n-1, -1, -1):\n",
    "            num = nums[i]\n",
    "            for j in range(32):\n",
    "                if num & (1<<j):\n",
    "                    cnt[j] = i\n",
    "            ans[i] = max(max(cnt), i)-i+1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 利利用或运算的性质（更通用的模板，可以求解更多问题：1、求出所有子数组的按位或结果，以及值等于该结果的子数组个数；2、求出按位或结果等于给出数字的子数组的最短/最长长度）。由于连续的或运算只会使更多的0变为1，且相同的或运算结果会处在相邻位置，所以可以合并相同的或运算结果，只维护第一次出现的下标来表示不同区间作为右端点的相同或运算结果。这样根据不同区间的下标就可以计算得到扩展问题1、2、的解。\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [0] * n\n",
    "        a = []\n",
    "        for i, x in enumerate(nums[::-1]):\n",
    "            a.append([i, x])\n",
    "            k = 0\n",
    "            for p in a:\n",
    "                p[1] |= x\n",
    "                if a[k][1] == p[1]:\n",
    "                    a[k][0] = p[0]\n",
    "                else:\n",
    "                    k += 1\n",
    "                    a[k] = p\n",
    "            a = a[:k + 1]\n",
    "            ans[n - 1 - i] = i - a[0][0] + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n",
    "        n=len(nums)\n",
    "        res=[0 for _ in range(n)]\n",
    "        ors=[]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            ors.append((0,i))\n",
    "            ors2=[]\n",
    "            for v,j in ors:\n",
    "                ors2.append((v|nums[i],j))\n",
    "            ors=[]\n",
    "            for v,j in ors2:\n",
    "                if ors and v==ors[-1][0]:\n",
    "                    ors[-1]=(v,j)\n",
    "                else:\n",
    "                    ors.append((v,j))\n",
    "            res[i]=ors[0][1]-i+1\n",
    "            # print(i,ors)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [0] * n\n",
    "        ors = []\n",
    "\n",
    "        for i in range(n-1, -1, -1):\n",
    "            ors.append([0, i])\n",
    "            num = nums[i]\n",
    "            # 更新\n",
    "            for j in range(len(ors)):\n",
    "                ors[j][0] |= num\n",
    "            # 合并\n",
    "            k = 0\n",
    "            for j in range(len(ors)):\n",
    "                if ors[j][0] != ors[k][0]:\n",
    "                    k += 1\n",
    "                    ors[k] = ors[j]\n",
    "                else:\n",
    "                    ors[k][1] = ors[j][1]\n",
    "            del ors[k+1:]\n",
    "            ans[i] = ors[0][1] - i + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\r\n",
    "        n = len(nums)\r\n",
    "        ors = []\r\n",
    "        res = [0] * n\r\n",
    "\r\n",
    "        for i in range(n - 1, -1, -1):\r\n",
    "            ors.append([0, i])\r\n",
    "            k = 0 \r\n",
    "            for p in ors:\r\n",
    "                p[0] |= nums[i]\r\n",
    "                if p[0] == ors[k][0]:\r\n",
    "                    ors[k][1] = p[1]\r\n",
    "                else:\r\n",
    "                    k += 1 \r\n",
    "                    ors[k] = p \r\n",
    "            del ors[k + 1:]\r\n",
    "            res[i] = ors[0][1] - i + 1\r\n",
    "        return res \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n",
    "\n",
    "        n = len(nums)\n",
    "        res = []\n",
    "        ors = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            x = nums[i]\n",
    "            ors.append([0, i])\n",
    "            k = 0\n",
    "            for p in ors:\n",
    "                p[0] |= x \n",
    "                if p[0] == ors[k][0]:\n",
    "                    ors[k][1] = p[1]\n",
    "                else:\n",
    "                    k += 1\n",
    "                    ors[k] = p \n",
    "            del ors[k+1:]\n",
    "            res.append(ors[0][1] - i + 1)\n",
    "        return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:   \n",
    "                def check(t,x):\n",
    "                    for j in range(31):\n",
    "                        if x >> j & 1 and t[j] <= 0:\n",
    "                            return False\n",
    "                    return True\n",
    "                n = len(nums)\n",
    "                ans = [n] * n\n",
    "                f = [0] * n\n",
    "                f[n-1] = nums[n-1]\n",
    "                for i in range(n-2,-1,-1):\n",
    "                    f[i] = f[i+1] | nums[i]\n",
    "                t = [0] * 32\n",
    "                l = 0\n",
    "                for r in range(n):\n",
    "                    for j in range(31):\n",
    "                        t[j] += (nums[r]>>j&1)\n",
    "                    while l <= r and check(t,f[l]):\n",
    "                        # print(l,r,f[l],t)\n",
    "                        ans[l] = min(r - l + 1,ans[l])\n",
    "                        for j in range(31):\n",
    "                            t[j] -= (nums[l]>>j&1)\n",
    "                        l += 1\n",
    "                        \n",
    "                while l < n:\n",
    "                    ans[l] = n - l\n",
    "                    l += 1\n",
    "                return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        tgt_lst = [0] * n\n",
    "        tgt_lst[-1] = nums[-1]\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            tgt_lst[i] = tgt_lst[i + 1] | nums[i]\n",
    "        max_tgt = max(tgt_lst)\n",
    "        m = len(bin(max_tgt)) - 2  \n",
    "        bc = [0] * m \n",
    "        cur_num = 0  \n",
    "        ans = [0] * n\n",
    "        j = -1\n",
    "        for i in range(n):\n",
    "            if i > 0:  \n",
    "                num = nums[i - 1]\n",
    "                num_bin = bin(num)[2:][::-1]\n",
    "                for k, c in enumerate(num_bin):\n",
    "                    if c == '1':\n",
    "                        bc[k] -= 1\n",
    "                        assert bc[k] >= 0\n",
    "                        if bc[k] == 0:\n",
    "                            mi = 2 ** k\n",
    "                            assert cur_num & mi\n",
    "                            cur_num -= mi\n",
    "            tgt = tgt_lst[i]\n",
    "            while cur_num < tgt:  \n",
    "                j += 1\n",
    "                assert j >= i\n",
    "                num = nums[j]\n",
    "                num_bin = bin(num)[2:][::-1]\n",
    "                for k, c in enumerate(num_bin):\n",
    "                    if c == '1':\n",
    "                        bc[k] += 1\n",
    "                        if bc[k] == 1:\n",
    "                            mi = 2 ** k\n",
    "                            assert cur_num & mi == 0\n",
    "                            cur_num |= mi\n",
    "            assert cur_num == tgt\n",
    "            j = max(i, j)  \n",
    "            ans[i] = j - i + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n",
    "        cnt = [deque() for _ in range(30)]\n",
    "        for i, x in enumerate(nums):\n",
    "            for k in range(30):\n",
    "                if x >> k & 1:  # x的第k位有1\n",
    "                    cnt[k].append(i)\n",
    "\n",
    "        ans = []\n",
    "        for i, x in enumerate(nums):\n",
    "            j = i\n",
    "            for k in range(30):\n",
    "                if cnt[k]:\n",
    "                    j = max(j, cnt[k][0])  # 最后一个1的位置\n",
    "                    if cnt[k][0] == i:  # 移除x自身第k位的1\n",
    "                        cnt[k].popleft()\n",
    "            ans.append(j - i + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from queue import PriorityQueue\n",
    "from typing import *\n",
    "from heapq import *\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = []\n",
    "        \n",
    "        a = [[] for _ in range(32)]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(32):\n",
    "                if (1 << j) & nums[i]:\n",
    "                    a[j].append(i)\n",
    "        for i in range(n):\n",
    "            p = i\n",
    "            for j in range(32):\n",
    "                if a[j]:\n",
    "                    p = max(p, a[j][-1])\n",
    "                    if a[j][-1] == i:\n",
    "                        a[j].pop()\n",
    "            ans.append(p-i + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n",
    "        L = len(nums)\n",
    "        rightORs = [0]*L\n",
    "        last = 0\n",
    "        posByBit = [[] for _ in range(32)]\n",
    "        bit2off = {\n",
    "            1<<i: i for i in range(32)\n",
    "        }\n",
    "        for i,n in enumerate(nums):\n",
    "            rightORs[L-1-i] = last = last | nums[L-1-i]\n",
    "            while n:\n",
    "                bit = n & -n\n",
    "                posByBit[bit2off[bit]].append(i)\n",
    "                n -= bit\n",
    "        res = [0]*L\n",
    "        for i, ror in enumerate(rightORs):\n",
    "            off = i\n",
    "            while ror:\n",
    "                bit = ror & -ror\n",
    "                lst = posByBit[bit2off[bit]]\n",
    "                off = max(off, lst[bisect_left(lst, i)])\n",
    "                ror -= bit\n",
    "            res[i] = off - i + 1\n",
    "        return res\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n",
    "        ans = [1] * len(nums)\n",
    "        maxOR = []\n",
    "        for i, x in enumerate(nums):\n",
    "            maxOR.append(x)\n",
    "            for j in range(i-1, -1, -1):\n",
    "                # 由于 i 是从左到右，所以当 nums[j] | x 的结果等于 nums[j] 后，\n",
    "                # 则说明再往前找，也找不到比 nums[j] 更大的了\n",
    "                # 因为 nusm[j] 表示的是 nums[0..j] 的最大或值。\n",
    "                if maxOR[j] | x == maxOR[j]:\n",
    "                    break\n",
    "                maxOR[j] |= x\n",
    "                ans[j] = i - j + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [0] * n\n",
    "        for i, x in enumerate(nums):\n",
    "            ans[i] = 1\n",
    "            for j in range(i-1, -1, -1):\n",
    "                if nums[j] | x == nums[j]:\n",
    "                    break\n",
    "                nums[j] |= x\n",
    "                ans[j] = i - j + 1\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n",
    "        n=len(nums)\n",
    "        ans=[1]*n\n",
    "        for i,x in enumerate(nums):\n",
    "            for j in range(i-1,-1,-1):\n",
    "                if (nums[j]|x)==nums[j]: break\n",
    "                nums[j]|=x\n",
    "                ans[j]=i-j+1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        result = [1]*n\n",
    "        for i in range(n):\n",
    "            for j in range(i-1,-1,-1):\n",
    "                if(nums[j] | nums[i] == nums[j]):\n",
    "                    break\n",
    "                nums[j] = nums[j] | nums[i]\n",
    "                result[j] = max(result[j], i-j+1)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 利用或运算的性质，由于每次或运算只会使为1的比特为变多而不会变少，所以可以正序枚举每个数nums[i]，向前做位运算，相当于合并nums[i]到nums[j]（j < i），如果nums[i] | nums[j] == nums[j]说明nums[i]是nums[j]的一个子集，那么无须再向前合并nums[i]到其它j < i下标，因为nums[i]前面的或运算结果就已经可以得到nums[i]了，j下标为了得到最大的或运算结果无须遍历到i，在i前面的某个下标就可以得到遍历到i的同样效果。\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [1] * n\n",
    "        for i in range(n):\n",
    "            for j in range(i-1, -1, -1):\n",
    "                if nums[i] | nums[j] == nums[j]:\n",
    "                    break\n",
    "                nums[j] |= nums[i]\n",
    "                ans[j] = i - j + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n",
    "        n=len(nums)\n",
    "        ans=[1]*n\n",
    "        for i,x in enumerate(nums):\n",
    "            for j in range(i-1,-1,-1):\n",
    "                if (nums[j]|x)==nums[j]: break\n",
    "                nums[j]|=x\n",
    "                ans[j]=i-j+1\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\r\n",
    "        ans = [0] * len(nums)\r\n",
    "        for i, x in enumerate(nums):\r\n",
    "            ans[i] = 1\r\n",
    "            for j in range(i - 1, -1, -1):\r\n",
    "                if (nums[j] | x) == nums[j]:\r\n",
    "                    break\r\n",
    "                nums[j] |= x\r\n",
    "                ans[j] = i - j + 1\r\n",
    "        return ans\r\n",
    "        \r\n",
    "    # 更通用模板\r\n",
    "    # 1. 求出所有子数组的按位或的结果，以及值等于该结果的子数组的个数。\r\n",
    "    # 2. 求按位或结果等于任意给定数字的子数组的最短长度/最长长度。\r\n",
    "    def smallestSubarrays2(self, nums: List[int]) -> List[int]:\r\n",
    "        n = len(nums)\r\n",
    "        ans = [0] * n\r\n",
    "        ors = []  # 按位或的值 + 对应子数组的右端点的最小值\r\n",
    "        for i in range(n - 1, -1, -1):\r\n",
    "            num = nums[i]\r\n",
    "            ors.append([0, i])\r\n",
    "            k = 0\r\n",
    "            for p in ors:\r\n",
    "                p[0] |= num\r\n",
    "                if ors[k][0] == p[0]:\r\n",
    "                    ors[k][1] = p[1]  # 合并相同值，下标取最小的\r\n",
    "                else:\r\n",
    "                    k += 1\r\n",
    "                    ors[k] = p\r\n",
    "            del ors[k + 1:]\r\n",
    "            # 本题只用到了 ors[0]，如果题目改成任意给定数值，可以在 ors 中查找\r\n",
    "            ans[i] = ors[0][1] - i + 1\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [0]*n\n",
    "        for i,x in enumerate(nums):\n",
    "            ans[i] = 1\n",
    "            for j in range(i - 1,-1,-1):\n",
    "                if nums[j] | x == nums[j]:\n",
    "                    break\n",
    "                nums[j] |= x\n",
    "                ans[j] = i - j + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [1] * n\n",
    "        for i in range(n):\n",
    "            x = nums[i]\n",
    "            for j in range(i-1, -1, -1):\n",
    "                res = nums[j] | x\n",
    "                if res != nums[j]:\n",
    "                    nums[j] = res\n",
    "                    ans[j] = i - j +1\n",
    "                else:\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n",
    "        n=len(nums)\n",
    "        ans=[0]*n\n",
    "        for i,x in enumerate(nums):\n",
    "            ans[i]=1\n",
    "            for j in range(i-1,-1,-1):\n",
    "                if (nums[j]|x)==nums[j]: break\n",
    "                nums[j]|=x\n",
    "                ans[j]=i-j+1\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n",
    "        n=len(nums)\n",
    "        ans=[0]*n\n",
    "        for i,x in enumerate(nums):\n",
    "            ans[i]=1\n",
    "            for j in range(i-1,-1,-1):\n",
    "                if (nums[j]|x)==nums[j]: break\n",
    "                nums[j]|=x\n",
    "                ans[j]=i-j+1\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n",
    "        ans = [0] * len(nums)  # 初始化结果数组\n",
    "        for i, x in enumerate(nums):  # 遍历nums数组\n",
    "            ans[i] = 1  # 设置ans[i]为1\n",
    "            for j in range(i - 1, -1, -1):  # 向后遍历所有在i之前的数字\n",
    "                if (nums[j] | x) == nums[j]:  # 检查是否需要进一步搜索\n",
    "                    break\n",
    "                nums[j] |= x  # 更新nums[j]\n",
    "                ans[j] = i - j + 1  # 更新ans[j]\n",
    "        return ans  # 返回结果数组\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n",
    "        ans = [1] * len(nums)\n",
    "        maxOR = []\n",
    "        for i, x in enumerate(nums):\n",
    "            maxOR.append(x)\n",
    "            for j in range(i-1, -1, -1):\n",
    "                \"\"\"\n",
    "                由于 i 是从左到右，所以当 maxOR[j] | x 的结果等于 maxOR[j] 后，\n",
    "                则说明再往前找，也找不到比 maxOR[j] 更大的了\n",
    "                因为 maxOR[j] 表示的是 nums[0..j] 的最大或值。\n",
    "                多个数字的或运算，意味着某一位上一旦有一个 1，那么这个位上就只会是 1 了\n",
    "                所以当 a | b = a 是，类似于 b 是 a 的子集，\n",
    "                因为 b 二进制上有 1 的位，在 a 上都有\n",
    "                \"\"\"\n",
    "                if maxOR[j] | x == maxOR[j]:\n",
    "                    break\n",
    "                maxOR[j] |= x\n",
    "                ans[j] = i - j + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n",
    "        ans = [1] * len(nums)\n",
    "        for i, x in enumerate(nums):            \n",
    "            for j in range(i-1, -1, -1):\n",
    "                # 由于 i 是从左到右，所以当 nums[j] | x 的结果等于 nums[j] 后，\n",
    "                # 则说明再往前找，也找不到比 nums[j] 更大的了\n",
    "                # 因为 nusm[j] 表示的是 nums[0..j] 的最大或值。\n",
    "                if nums[j] | x == nums[j]:\n",
    "                    break\n",
    "                nums[j] |= x\n",
    "                ans[j] = i - j + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n",
    "        ans=[0]*len(nums)\n",
    "        for i,x in enumerate(nums):\n",
    "            ans[i]=1\n",
    "            for j in range(i-1,-1,-1):\n",
    "                if (nums[j]|x)==nums[j]:\n",
    "                    break \n",
    "                nums[j]|=x  \n",
    "                ans[j]=i-j+1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n",
    "        ans = [0]*len(nums)\n",
    "        for i,x in enumerate(nums):\n",
    "            ans[i] = 1\n",
    "            for j in range(i-1,-1,-1):\n",
    "                if (nums[j]|x) == nums[j]:\n",
    "                    break\n",
    "                nums[j] |= x\n",
    "                ans[j] = i-j+1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n",
    "        ans = [0] * len(nums)\n",
    "        for i, x in enumerate(nums):\n",
    "            ans[i] = 1\n",
    "            for j in range(i - 1, -1, -1):\n",
    "                if (nums[j] | x) == nums[j]:\n",
    "                    break\n",
    "                nums[j] |= x\n",
    "                ans[j] = i - j + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n",
    "        ans = [0]*len(nums)\n",
    "        for i,x in enumerate(nums):\n",
    "            ans[i] = 1\n",
    "            for j in range(i-1,-1,-1):\n",
    "                if (nums[j]|x) == nums[j]:\n",
    "                    break\n",
    "                nums[j] |= x\n",
    "                ans[j] = i-j+1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n",
    "        ans = [0] * len(nums)\n",
    "        for i, x in enumerate(nums):\n",
    "            ans[i] = 1\n",
    "            for j in range(i - 1, -1, -1):\n",
    "                if (nums[j] | x) == nums[j]:\n",
    "                    break\n",
    "                nums[j] |= x\n",
    "                ans[j] = i - j + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n",
    "        ans = [0] * len(nums)\n",
    "        for i, x in enumerate(nums):\n",
    "            ans[i] = 1\n",
    "            for j in range(i - 1, -1, -1):\n",
    "                if (nums[j] | x) == nums[j]:\n",
    "                    break\n",
    "                nums[j] |= x\n",
    "                ans[j] = i - j + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubarrays(self, nums: List[int]) -> List[int]:\n",
    "        ans = [0] * len(nums)\n",
    "        for i, x in enumerate(nums):\n",
    "            ans[i] = 1\n",
    "            for j in range(i - 1, -1, -1):\n",
    "                if (nums[j] | x) == nums[j]:\n",
    "                    break\n",
    "                nums[j] |= x\n",
    "                ans[j] = i - j + 1\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
